1. Field of the Invention
This invention relates generally to an image compression technique, and more particularly to an image compression technique that uses patterns of previously-coded neighboring pixels to predict and code each pixel. Still more particularly, the image compression technique of the present invention uses the neighboring pixel patterns to capture the number of distinct colors present in each of these pixels as well as the extent of these colors in corresponding directions.
2. Description of the Related Art
A typical high quality digitized color image may use 24 bits per pixel (bpp)--8 bits for each of the three basic color components: red (R), green (G) and blue (B) in RGB color space or for each of the three basic luminance-chrominance components: luminance (Y), chrominance (C.sub.B) and chrominance (C.sub.R) in YC.sub.B C.sub.R color space. To transmit or store such images in the uncompressed state (i.e., in the spatial or pixel domain) is simply too costly in terms of time and memory requirements. Thus, applications and devices which store or transmit high quality digitized color images typically do so in a compressed format, using one of the currently available compression techniques.
Various image compression techniques have been proposed to reduce the amount of data used to represent a digitized color image while, at the same time, providing quality image representation. How much the image is compressed, given in terms of a compression ratio, depends on the image itself, the technique used and the amount of information loss that can be tolerated. Some of these techniques are "lossless," meaning that they preserve all information of the original image so that it is reproduced exactly when the data is decompressed. Other techniques, commonly referred to as "lossy," discard information which is visually insignificant. By only approximating the original image (rather than reproducing it, exactly), lossy techniques are generally able to produce higher compression ratios than lossless techniques. In selecting the appropriate compression technique and compression ratio, the user must consider the particular image to be compressed, the desired image quality as well as transmission time and memory requirements, with the understanding that higher compression ratios lead to lower transmission times and memory requirements but also produce lower quality images.
Of the lossless image compression techniques presently available, some employ predictive coding models. In general, these techniques were designed for continuous-tone, "natural" images, and not for palettized, "synthetic" images, such as computer-generated graphics, street maps, clip-art and the like, which have several sharply delineated uniform-color regions with overlaid text and symbols. A palettized color image consists of a color look-up table, with the value of each pixel stored as an index into the table. When used on palettized images, these predictive compression techniques, which include CALIC and JPEG-LS among others, operate to compress each of the R, G and B planes of the image separately, after expanding each palette index into its actual color values. For each of the three color planes, the pixels are scanned and coded in raster-order. During this process, the values of neighboring pixels that have already been scanned and coded are used to determine a context and to predict the current pixel using a context-dependent formula. The error between the actual value of the current pixel and its predicted value is then coded by a context-dependent entropy encoder.
One of the problems associated with these predictive techniques is the inherent inefficiency which results from compressing each of the three color planes separately. Another problem is that these predictive techniques generally do not work well on palettized images directly, because, if palette indices are used, prediction formulas tend to become meaningless since palette indices for neighboring pixels may have no correlation at all. In fact, palettized images can typically be compressed more using non-predictive techniques, such as GIF and PNG (without the "filtering" mode), compared to predictive techniques, such as
JPEG-LS, PNG (with "filtering" on) and UCM. There has been some work done on reordering the palette to make the predictive coding techniques more effective on palettized images. With such reordering, the predictive techniques achieve significantly better compression on most images. However, for street-map images, the inventor herein has found that only very sophisticated CALIC and UCM algorithms could achieve better compression than the non-predictive PNG algorithm, and that too only after reordering the palette.
Some specific patents directed to data compression techniques that use previously-coded neighboring pixels to predict the current pixel are discussed below. For example, U.S. Pat. No. 5,020,121 proposes a method for compression of language characters or two level images on a computer screen. A character or symbol is represented on a block of pixels which is decomposed into a plurality of nonoverlapping sub-blocks. The known pixel configuration of neighborhood pixels is used to predict the most probable pixel configuration for the target sub-block based on statistical analysis of the sub-block pixel configurations for all characters in the set. U.S. Pat. No. 5,682,152 incorporates lossless entropy encoding into a lossy compression system. Image data is decorrelated into a baseband and multiple subbands. Pixels in those bands are then coded using neighboring pixels. U.S. Pat. No. 5,680,129 proposes a lossless image compression technique which uses a context quantizer that determines a context for the current pixel to be coded from previously-coded neighboring pixels.
U.S. Pat. No. 5,471,207 provides for the compression of palettized images using an entropy encoder. Input symbols in an M-ary alphabet are binarized based on a context model of the input data. Binarization is determined from a reindexing table which maps each input symbol to a number of binary values. The mapping of the reindexing table is determined from the images to be compressed and is transmitted with the compressed images as overhead.
Other patents directed to various techniques for compression of image data include U.S. Pat. No. 5,497,434 wherein a compressor searches for matching pixel strings in previous and current frames. If a match is found, the compressor outputs the most appropriate pixel code. Otherwise, the unmatched pixel count is incremented. The technique employed in U.S. Pat. No. 5,615,287 involves the compression of an image by subtracting a filled edge array from an image array to generate a difference array. In U.S. Pat. No. 5,659,631 image compression is achieved by coding color planes of the image. The color planes are ordered by density and the densest plane is coded first. Other color planes are then coded but pixels known to have colors from previously coded planes are not coded. The last color plane is not coded but is deduced from all of the other color planes.
However, none of these patents provide a compression technique wherein the neighboring pixel patterns are used to predict and code a current pixel by capturing the number of distinct colors present in the neighboring pixels as well as the extent of these colors in the corresponding directions of each of the pixels.